package chapter19;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 斐波拉契堆
 * <p>
 * 两种用途：
 * 1.支持可合并堆的各种操作
 * 2.在常数摊还时间内完成,适用于操作频繁的数据机构
 * <p>
 * 可合并堆：
 * make-heap()：创建和返回一个新的不含任何元素的堆
 * insert(H,x)：将一个已填入关键字的元素x插入堆H中
 * minimum(H)：返回一个指向堆H中具有最小关键字元素的指针
 * extract-min(H)：从堆H中删除最小关键字的元素，并返回一个指向该元素的指针
 * union(H1,H2)：创建并返回一个包含堆H1和H2中所有元素的新堆。堆H1和H2由这一操作销毁
 * -斐波拉契堆还支持：
 * decrease-key(H,x,k)：将堆H中元素x的关键字赋予新值k。假定新值k不大于当前的关键字
 * delete(H,x)：从堆H中删除x
 */
public class FibHeap {

    /**
     * 新增都是在根链表上
     */
    public static void insert(RootNode H, Node x) {
        x.degree = 0;
        x.p = null;
        x.mark = false;
        if (H.min == null) {
            H.root.add(x);
            H.min = x;
        } else {
            H.root.add(x);
            if (x.key < H.min.key) {
                H.min = x;
            }
        }
        H.n++;
    }

    /**
     * 从根节点开始合并，将原有的合并到新的根节点
     */
    public static RootNode union(RootNode H1, RootNode H2) {
        RootNode H = new RootNode();
        H.min = H1.min;
        H.root = H1.root;
        H.root.addAll(H2.root);
        if (H1.min == null || (H2.min != null && H2.min.key < H1.min.key)) {
            H.min = H2.min;
        }
        H.n = H1.n + H2.n;
        return H;
    }

    /**
     * 1.把最小节点的堆黑拆散，全部挂到根节点链表上，
     * 2.把最小的节点给删除
     * 3.重新找到最小节点，给H.min赋值
     * 4.对于剩下的节点进行合并
     */
    public static Node extractMin(RootNode H) {
        Node z = H.min;
        if (z != null) {
            List<Node> nodes = z.child;
            for (Node x : nodes) {
                H.root.add(x);
                x.p = null;
            }
            int i = H.root.indexOf(z);
            H.root.remove(z);
            if (H.root.size() == 0) {
                H.min = null;
            } else {
                if (i - 1 >= 0) {
                    H.min = H.root.get(i - 1);
                } else {
                    H.min = H.root.getLast();
                }
                consolidate(H);
            }
            H.n--;
        }
        return z;
    }

    /**
     * 合并：
     * 1.在根链表找到两个具有相同度数的根x和y，不失一般性，x.key<=y.key
     * 2.把y连接到x：从根链表中移除y，调用 link 过程，使y成为x的孩子，该过程如果A[i]=y，那么当前的y是一个具有y.degree=i的根
     * <p>
     * A[D(H.n)]辅助记录根节点对应的度数的轨迹。如果A[i]=y，那么当前的y是一个具有y.degree=i的根。
     */
    private static void consolidate(RootNode H) {
        Node[] A = new Node[D(H.n) + 1];
        List<Node> root = new ArrayList<>(H.root);

        List<Node> deleted = new ArrayList<>();
        for (Node w : root) {
            Node x = w;
            int d = x.degree;
            while (A[d] != null) {
                Node y = A[d];
                if (deleted.contains(y)) {
                    break;
                }
                if (x.key > y.key) {
                    Node temp = x;
                    x = y;
                    y = temp;
                }
                link(H, x, y);
                deleted.add(y);
                A[d] = null;
                d++;
            }
            A[d] = x;
        }
        H.min = null;
        for (int i = 0; i <= D(H.n); i++) {
            if (A[i] != null) {
                if (H.min == null) {
                    H.root = new LinkedList<>();
                    H.root.add(A[i]);
                    H.min = A[i];
                } else {
                    H.root.add(A[i]);
                    if (A[i].key < H.min.key) {
                        H.min = A[i];
                    }
                }
            }
        }
    }

    private static void link(RootNode H, Node x, Node y) {
        H.root.remove(y);
        x.child.add(y);
        x.mark = true;
        x.degree++;
        y.mark = false;
    }

    private static int D(int n) {
        return (int) Math.ceil(Math.log(n) / Math.log(2));
    }

    public static void decreaseKey(RootNode H, Node x, int k) {
        if (k > x.key) {
            return;
        }
        x.key = k;
        Node y = x.p;
        if (y != null && x.key < y.key) {
            cut(H, x, y);
            cascadingCut(H, y);
        }
        if (x.key < H.min.key) {
            H.min = x;
        }
    }

    /**
     * 将x从y上切除,移动到根链表上,使得x为根节点
     * <p>
     * *     y
     * *    /
     * *   x
     */
    private static void cut(RootNode H, Node x, Node y) {
        y.child.remove(x);
        y.degree--;
        H.root.add(x);
        x.p = null;
        x.mark = false;
    }

    /**
     * 级联切除,使得父节点是为空或者是为被mark的节点
     */
    private static void cascadingCut(RootNode H, Node y) {
        Node z = y.p;
        if (z != null) {
            if (!y.mark) {
                y.mark = true;
            } else {
                cut(H, y, z);
                cascadingCut(H, z);
            }
        }
    }

    /**
     * 将x设置为最小值，然后弹出
     */
    public static void delete(RootNode H, Node x) {
        decreaseKey(H, x, Integer.MIN_VALUE);
        extractMin(H);
    }

}
